package Tree;

import java.util.Stack;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2024/08/28
 * 栈实现二叉树
 */
public class StackBinaryTree {
    /**
     * 内部类
     */
    private static class Node {
        Integer data;
        StackBinaryTree.Node left;
        StackBinaryTree.Node right;

        public Node(Integer data) {
            this.data = data;

        }
    }

    private static void pre(Node node) {
        //java内部的栈实现类
        Stack<Node> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            /**弹出栈顶的元素
             *node:新的子数的头节点
             */
            node = stack.pop();

            //先序遍历
            System.out.println(node.data);

            //判断子树头节点的右节点是否为空
            if (node.right != null) {
                //先将右节点压入栈中
                stack.push(node.right);
            }
            //再判断子树头节点的左节点是否为空
            if (node.left != null) {
                //再将左节点压入栈中
                stack.push(node.left);
            }
        }
    }

    public static void main(String[] args) {
        StackBinaryTree.Node root = new StackBinaryTree.Node(1);
        root.left = new StackBinaryTree.Node(2);
        root.right = new StackBinaryTree.Node(3);
        root.left.left = new StackBinaryTree.Node(4);
        root.left.right = new StackBinaryTree.Node(5);
        root.right.left = new StackBinaryTree.Node(6);
        root.right.right = new StackBinaryTree.Node(7);


        //测试
        pre(root);
    }
}
